1. Technical Field
The present invention relates generally to the automated layout of integrated circuits. In particular, the present invention is directed toward automatic, optimized insertion of buffers into integrated circuit routing trees.
2. Description of Related Art
In recent years, it has become commonplace for integrated circuit designers to build an integrated circuit layout from libraries of reusable high-level modules, sometimes referred to as “macro blocks.” Proprietary macro blocks are often referred to as “intellectual property blocks” (“IP blocks”), to emphasize their relatively intangible, yet proprietary nature. Computerized integrated circuit design tools may be used to store, retrieve, and combine macro blocks into complete integrated circuits. This design philosophy of combining reusable macro blocks to produce a complex integrated circuit is known as “system-on-a-chip” (SoC) design. Designing a “system-on-a-chip” involves designing the interconnections between macro blocks. Despite the apparent simplicity of SoC design, this is often not a trivial task. The reason for this is that the connections themselves are physical components (i.e., wires) with non-ideal properties. Like all electrical conductors, integrated circuit connections suffer from delay and signal loss due to physical properties such as resistance, capacitance, and relativistic limitations on the speed at which electrons are able to travel. In order to ensure that all components in an integrated circuit are properly synchronized to work properly, it is important to take these factors into account when designing interconnections between macro blocks to minimize signal loss and to allow operation within acceptable timing specifications.
Buffer insertion is now widely recognized as a key technology for improving VLSI (Very Large Scale Integration) interconnect performance. For a buffer insertion technique to be effective, however, it must be fully aware of its surrounding blockage constraints while also being efficient enough to quickly process thousands of nets. In the buffer insertion literature, van Ginneken's dynamic programming based algorithm has established itself as a classic in the field. Van Ginneken's algorithm is described in L. P. P. van Ginneken, “Buffer placement in distributed RC-tree networks for minimal Elmore delay,” Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 865-868, 1990, which is hereby incorporated by reference. Van Ginneken's algorithm assumes a Steiner tree routing topology and inserts buffers into the Steiner tree so as to minimize Elmore delay. A Steiner tree is defined as follows: If, in a weighted graph, a subset of the vertices are designated as “terminals,” a Steiner tree is a minimum-weight connected subgraph which includes all of the “terminals.” Thus, for example, a minimum spanning tree of a graph is a special case of a Steiner tree in which all of the vertices in the graph are selected as terminals.
Prior to buffer insertion, several large area chunks may be already occupied by macro or IP blocks for which wires can be routed over the blocks, but buffers cannot be inserted inside the blocks. We call these regions “buffer blockages.” For example, FIG. 1A shows a Steiner tree with 3-pins and a buffer blockage. Let the required arrival times for the sinks be rat(υ1)=200 and rat(υ2)=100. If the blockage is ignored, one can obtain a good solution as shown in FIG. 1B. Here the buffer acts to decouple the load from the υ1 branch to the more critical sink υ2. Of course, in practice, one cannot ignore the buffer blockage and a solution other than that in FIG. 1B must be sought. If one restricts the solution space to the existing Steiner topology, the two best solutions are shown in FIGS. 1C and 1D, but neither solution meets the required timing constraints (i.e., the amount of timing slack allowed is negative, meaning that the timing constraints will be exceeded; a positive slack denotes a solution that fits within specified timing constraints).
A number of papers, including H. Zhou, D. F. Wong, I-M. Liu, and A. Aziz, “Simultaneous routing and buffer insertion with restrictions on buffer locations,” Proceedings of the ACM/IEEE Design Automation Conference, pp. 96-99, 1999; A. Jagannathan, S.-W. Hur, and J. Lillis, “A fast algorithm for context-aware buffer insertion,” Proceedings of the ACM/IEEE Design Automation Conference, pp. 368-373, 2000; and M. Lai and D. F. Wong, “Maze routing with buffer insertion and wiresizing,” Proceedings of the ACM/IEEE Design Automation ACM/IEEE Design Automation Conference, pp. 374-378, 2000, propose optimal algorithms for finding a minimum delay buffered path with buffer blockages. In J. Cong and X. Yuan, “Routing tree construction under fixed buffer locations,” Proceedings of the ACM/IEEE Design Automation Conference, pp. 379-384, 2000, Cong and Yuan proposed a dynamic programming algorithm, called RMP, to handle the multi-sink net buffer insertion with location restrictions. RMP is designed for the buffer block methodology for which the number of legal buffer locations is quite limited. The buffer block methodology is described in J. Cong, T. Kong, and D. Z. Pan, “Buffer block planning for interconnect-driven floorplanning,” Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 358-363, 1999. RMP works on a grid graph that is constructed by adding horizontal and vertical lines through each potential buffer locations to the Hanan grid. It not only explores almost every node on the grid in tree construction but also considers many sink combinations in subsolutions. Consequently, RMP tends to be slow when either the number of net pins or legal buffer locations is large. Nevertheless, RMP generally yields near optimal solutions in term of timing performance. More recently, Tang et al. suggested a graph-based algorithm on a similar problem in X. Tang, R. Tian, H. Xiang, and D. F. Wong, “A new algorithm for routing tree construction with buffer insertion and wire sizing under obstacle constraints,” Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 49-56, 2001. While more efficient than RMP, it can optimize only the maximum sink delay rather than the minimum slack.
Difficult buffering problems occur not just with large nets but also when sink polarity constraints are present. Alpert et al. developed the “buffer-aware” C-Tree heuristic to be used as a precursor to van Ginneken's algorithm. The C-Tree heuristic is described in C. J. Alpert, G. Gandham, M. Hrkic, J. Hu, A. B. Kahng, J. Lillis, B. Liu, S. T. Quay, S. S. Saptnekar, and A. J. Sullivan, “Buffered Steiner Trees for Difficult Instances,” IEEE Transactions on Computer-Aided Design, vol. 21, no. 1, January 2002, pp. 3-14, which is hereby incorporated by reference. The C-Tree method is not “blockage-aware,” however. To solve this problem, one could first run C-Tree, then invoke the algorithm of C. J. Alpert, G. Gandham, J. Hu, J. L. Neves, S. T. Quay, and S. S. Sapatnekar, “Steiner Tree Optimization for Buffers, Blockages, and Bays,” IEEE Transactions on Computer-Aided Design, vol. 20, no. 4, April 2001, pp. 556-562, hereby incorporated by reference, which performs local re-routing to avoid the blockages without adding too much wiring. Then, one could pass this modified tree to van Ginneken's buffer insertion algorithm. For example, this approach would obtain the buffered solution in FIG. 1E. However, a carefully constructed timing-driven topology can be destroyed by these local topology changes, making the final slack worse than not running local rerouting at all.
Thus, a need exists for a fast and effective technique for performing optimal buffer insertion on multi-sink nets.